package huffmanTree.std02;

import huffmanTree.std01.HuffmanTree;

import java.nio.charset.StandardCharsets;
import java.util.*;

/**
 * 哈夫曼 编码
 * i like like like java do you like a java
 * 分析：
 * d:1 y:1 u:1j:2 v:2 0:2 1:4 k:4 e:4 i:5 a:5 :9
 *  因为要符合前缀编码 也就是 比如 d:1011 那么 其他代表里 就不能以1011 开头的
 *  次数代表权值 构成哈夫曼 路径左代表0 右边1 构成的码 就不会存在 前缀
 * @author yinb
 */
public class HuffmanZip {
    /**
     * 1. 给定字符串 分析 各个字符出现的次数 用map
     * 2. map 循环 构建 node 节点
     * 3. 构建哈弗曼树
     * 4. 创建各个字符 对应的 01 码
     * 5. 拼接各码 得到 原码
     * 6. 压缩 8位一个byte 组成 由各8位组成的 字符
     */
    public static void main(String[] args) {
        String str = "i like like like java do you like a java";
        System.out.println(str.length());
        List<Byte> bytes = huffmanZip(str);
        System.out.println("压缩后：：：" + bytes);

        /**
         * 解压 返回
         * 1.先将 bytes 数组 返回 拼接成原 字符 1010100010111111。。。。
         * 2.再返回到 byte数组
         */
        Map<Byte, String> huffmanCode = huffmanCode(str);
        byte[] a = unZip(huffmanCode, bytes);
        System.out.println("解压后：：" +new String(a));

    }

    public static byte[] unZip( Map<Byte, String> huffmanCode,List<Byte> bytes ){
        //第一步 先返回  1010100010111111。。。。
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < bytes.size(); i++) {
            boolean flag = true;
            if(i == bytes.size()-1){
                flag = false;
            }
            str.append(byteToBitString(flag,bytes.get(i)));
        }
        System.out.println(str);
        //第二步 先将huffmanCode 反转下
        Map<String,Byte> map = new HashMap<>();
        huffmanCode.forEach((k,v)->{
            map.put(v,k);
        });
        System.out.println(map);
        //第三步 就要遍历字符串  返回byte[]
        List<Byte> res = new ArrayList<>();
        int lastIndex = 0;
        for (int i = 0; i <= str.length(); i++) {
            String item = str.substring(lastIndex,i);
            if(null != map.get(item)){
                res.add(map.get(item));
                lastIndex = i;
            }
        }

        byte[] a = new byte[res.size()];
        for (int i = 0; i < res.size(); i++) {
            a[i] = res.get(i);
        }
        return a;
    }

    /**
     *
     * @param flag true:需要补齐8位  false: 不需要补齐
     * @param b 压缩后的 byte
     * @return 返回 byte 对应的 01
     */
    private static String byteToBitString(boolean flag,byte b){
        int temp = b;
        //如果 b 是正数 则 需要将前面补齐 257: 1 0000 0000  如果 b=1 补齐：0000 0001
        if(flag){
            temp |= 256;
        }
        //返回的是补码
        String s = Integer.toBinaryString(temp);
        if (flag){
            return s.substring(s.length()-8);
        }
        return s;
    }

    private static Map<Byte,String> huffmanCode(String str){
        List<Node> charAndCountNode = getCharAndCountNode(str);
        //构建哈夫曼树
        Node huffmanARoot = getHuffmanARoot(charAndCountNode);
        //构建编码 左0 右1  map
        Map<Byte,String> byteCode = new HashMap<>();
        getCodes(byteCode,huffmanARoot,new StringBuilder(),"");
        return byteCode;
    }




    private static List<Byte> huffmanZip(String str) {
        Map<Byte, String> byteStringMap = huffmanCode(str);
        System.out.println(byteStringMap);
        //整理 拼接
        String strCode = getStrCode(str, byteStringMap);
        System.out.println(strCode);
        //数据压缩 总计133 用位来表示 一个byte 8 位
        List<Byte> bytes = getBytes(strCode);
        return bytes;
    }

    public static List<Byte> getBytes(String strCode){
        List<Byte> bytes = new ArrayList<>();
        int len = (strCode.length() + 7 ) / 8;
        for (int i = 0; i < strCode.length()  ; i+=8) {
            String substring = "";
            if(i+8 > strCode.length()){
                substring = strCode.substring(i, strCode.length());
            }else {
                substring = strCode.substring(i, i+8);
            }
            bytes.add((byte) Integer.parseInt(substring, 2));
        }
        return bytes;
    }

    public static String getStrCode(String str,Map<Byte,String> byteCode){
        StringBuilder builder = new StringBuilder();
        byte[] bytes = str.getBytes();
        for (Byte b:bytes) {
            if(null != byteCode.get(b)){
                builder.append(byteCode.get(b));
            }
        }
        return builder.toString();
    }

    /**
     * 前序遍历 根 左 右
     * @param root
     */
    public static void preOut(Node root){
        System.out.print(root.weight +"-" + root.date +"  ");
        if(null != root.leftNode){
            preOut(root.leftNode);
        }
        if (null != root.rightNode){
            preOut(root.rightNode);
        }
    }






    public static void getCodes(Map<Byte,String> byteStringMap,Node huffmanARoot,StringBuilder str,String code){
        StringBuilder str2 = new StringBuilder(str);
        str2.append(code);
        if(null != huffmanARoot.date){
            byteStringMap.put(huffmanARoot.date,str2.toString());
        }else {
            if(null != huffmanARoot.leftNode ){
                getCodes(byteStringMap,huffmanARoot.leftNode ,str2,"0");
            }
            if(null != huffmanARoot.rightNode ){
                getCodes(byteStringMap,huffmanARoot.rightNode ,str2,"1");
            }
        }
    }


    public static Node getHuffmanARoot(List<Node> charAndCountNode){
        while (charAndCountNode.size()>1){
            //将node 从小到大排序
            Collections.sort(charAndCountNode);
            //取出 最小的两个节点
            Node leftNode = charAndCountNode.get(0);
            Node rightNode = charAndCountNode.get(1);
            // 相加 然后将值放入到数组 并删除两个节点 并重复2 3 操作
            Node newNode = new Node(leftNode.weight+rightNode.weight,null);
            newNode.leftNode = leftNode;
            newNode.rightNode = rightNode;
            charAndCountNode.remove(leftNode);
            charAndCountNode.remove(rightNode);
            charAndCountNode.add(newNode);
        }
        return charAndCountNode.get(0);
    }

    /**
     * 获取 每个字符的权重 的node
     * @param str 字符
     * @return
     */
    public static List<Node> getCharAndCountNode(String str){
        Map<Byte,Integer> map = new HashMap<>();
        List<Node> nodes = new ArrayList<>();
        byte[] bytes = str.getBytes();
        for (Byte b:bytes) {
            if(Objects.isNull(map.get(b))){
                map.put(b,1);
            }else {
                map.put(b,map.get(b)+1);
            }
        }
        map.forEach((k,v)->{
            Node node = new Node(v,k);
            nodes.add(node);
        });
        return nodes;
    }

    static class Node implements Comparable<Node>{
        int weight;// 权重
        Byte date; // 数据
        Node leftNode;
        Node rightNode;

        public Node(int weight, Byte date) {
            this.weight = weight;
            this.date = date;
        }

        @Override
        public int compareTo(Node o) {
            return weight - o.weight;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "date=" + date +
                    ",weight=" + weight +
                    '}';
        }
    }

}

